package me.huangxiang.data_structure_and_algorithm.search;

public class BinSearch {
    static long compareCount = 0;

    public static int binSearchNoRecursion(int[] A, int target){
        compareCount = 0; // 用来记录不同二分查找方法进行的次数
        int left = 0;
        int right = A.length - 1;

        while (left <= right){
            compareCount++;
            // 未考虑数据的统计特性
            int middle = left + ((right - left) >> 1);
            if (A[middle] > target){
                right = middle - 1;
            } else if (A[middle] < target){
                left = middle + 1;
            } else {
                return middle;
            }
        }
        return -1;
    }


    public static int binSearchRecursion(int[] A, int target, int l, int r){
        if (r < l){
            return -1;
        }
        int middle = l + ((r - l) >> 1);
        if (A[middle] == target){
            return middle;
        }else if (A[middle] < target){
            return binSearchRecursion(A, target,middle + 1, r);
        }else {
            return binSearchRecursion(A, target, l, middle - 1);
        }
    }

    public static int enhancedBinSearch(int[] A, int target){
        compareCount = 0;
        int left = 0;
        int right = A.length - 1;

        while (left <= right){
            compareCount++;
            // 归一化处理，考虑了数据的统计特性
            int middle = left + (right - left) * (target - A[left]) / (A[right] - A[left]);
            if (A[middle] > target){
                right = middle - 1;
            } else if (A[middle] < target){
                left = middle + 1;
            } else {
                return middle;
            }
        }
        return -1;
    }
}
